//给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 
//
// 注意: 
//
// 
// 可以认为区间的终点总是大于它的起点。 
// 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。 
// 
//
// 示例 1: 
//
// 
//输入: [ [1,2], [2,3], [3,4], [1,3] ]
//
//输出: 1
//
//解释: 移除 [1,3] 后，剩下的区间没有重叠。
// 
//
// 示例 2: 
//
// 
//输入: [ [1,2], [1,2], [1,2] ]
//
//输出: 2
//
//解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
// 
//
// 示例 3: 
//
// 
//输入: [ [1,2], [2,3] ]
//
//输出: 0
//
//解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
// 
// Related Topics 贪心 数组 动态规划 排序 
// 👍 541 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.Collections;

public class NonOverlappingIntervals {
    public static void main(String[] args) {
        Solution solution = new NonOverlappingIntervals().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 贪心算法的经典题目
         * 1.排序：可以按照左边界排，也可以按照右边界排，两种方法逻辑是不一样的
         * 2.遍历，根据排序的方式不同，遍历的方式也会有所不同
         * 3.统计个数，可以统计重复区间个数，也可以统计非重复区间个数
         * 4.求非重复区间时分割点的选取
         *
         * 代码实现：排序以及之后的选择体现了贪心，每次选右边界最小的就是为了之后可以添加更多区间
         *  1.按照有区间递增进行的排序，右边界小的时候可以为后边留下更大的区间
         *  （右边界相同时按照左边界升序，这样使得区间最大）
         *  2.首先选取第一个区间的右边界为分界线，遍历剩下的区间，不重叠的话就更新边界
         *    重叠的话就进行统计
         *
         * 如果按照左边界排的话就是从右向左遍历就好了，每次比较左边界
         */
        public int eraseOverlapIntervals(int[][] intervals) {
            Arrays.sort(intervals,(a,b)->{
                //先按照有边界来进行升序排列，右边界相同的话按照左边界升序排列
                if (a[1]!=b[1]){
                    return a[1]-b[1];
                }else return a[0]-b[0];
            });
            int res = 0;
            int edge = intervals[0][1];//当前无重叠区间的右边界
            for (int i = 1; i < intervals.length ; i++) {
                if (intervals[i][0]<edge) res++;//如果当前区间发生了重叠，记录
                else edge = intervals[i][1];//没有重叠的话就更新边界
            }
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}